package leetcode.hot100;

import datastruct.list.ListNode;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution148 {

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        ListNode cur = head;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(1);
        cur = cur.next;
        cur.next = new ListNode(3);
        cur = cur.next;
        ListNode listNode = new Solution148().sortList(head);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    public ListNode sortList(ListNode head) {
        //归并排序，为了尽快找到中间的节点，采用快慢指针，每次拆分后都把每段的最后一个元素next置为null
        //递归终止条件：当前节点无后续
        if(head==null||head.next==null) return head;
        //拆分
        ListNode fast = head.next, slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow在整段链表中间
        ListNode rightSegHead = slow.next; //分出的右段头节点
        slow.next = null; //分出的左边段头节点就是head，末尾为null
        //分别对左右两段递归
        ListNode leftHead = sortList(head);
        ListNode rightHead = sortList(rightSegHead);
        //合并
        ListNode virHead = new ListNode(0); //为了方便，这里需要一个虚拟的头节点
        ListNode cur = virHead;
        while(leftHead!=null&&rightHead!=null){
            if(leftHead.val<rightHead.val){
                cur.next = leftHead;
                cur = cur.next;
                leftHead = leftHead.next;
            }else{
                cur.next = rightHead;
                cur = cur.next;
                rightHead = rightHead.next;
            }
        }
        if(leftHead!=null) cur.next = leftHead;
        if(rightHead!=null) cur.next = rightHead;

//        ListNode tmp = virHead.next;
//        while (tmp!=null){
//            System.out.print(tmp.val);
//            tmp = tmp.next;
//        }
//        System.out.println();

        return virHead.next;
    }

    public ListNode sortList1(ListNode head) {
        ArrayList<Integer> tmp = new ArrayList<>();
        ListNode cur = head;
        while(cur!=null){
            tmp.add(cur.val);
            cur = cur.next;
        }
        Integer[] record = (Integer[]) tmp.toArray();
        Arrays.sort(record);
        cur = head;
        for (int i = 0; i < record.length; i++) {
            cur.val = record[i];
            cur = cur.next;
        }
        return head;
    }
}
